#include "strStr2.h"
#include <string.h>
#include <stdlib.h>
int strStr(char *haystack, char *needle){
    int hLen = strlen(haystack), nLen = strlen(needle);
    
    if(nLen == 0){
        return 0;
    }

    int *pi = malloc(sizeof(*pi) * nLen);

    for(int i = 1, j = 0; i < nLen; i++){
        while(j > 0 && needle[i] != needle[j]){
            j = pi[j - 1];
        }

        if(needle[i] == needle[j]){
            j++;
        }

        pi[i] = j;
    }

    for(int i = 0, j = 0; i < hLen; i++){
        while(j > 0 && needle[j] != haystack[i]){
            j = pi[j - 1];
        }

        if(needle[j] == haystack[i]){
            j++;
        }
        if(j == nLen){
            return i - nLen + 1;
        }
    }
    return -1;
}